package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N二叉树的序列化与反序列化297.java
 * @Description https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 * @createTime 2021年04月20日 12:58:00
 */
public class N二叉树的序列化与反序列化297 {
    // Encodes a tree to a single string.
    StringBuilder stringBuilder = new StringBuilder();

    public String serialize(TreeNode root) {
        //使用先序遍历的方式来进行
        preSerialize(root, stringBuilder);
        return stringBuilder.toString();
    }

    private void preSerialize(TreeNode root, StringBuilder builder) {
        if (root == null) {
            builder.append("#").append(",");
            return;
        }
        builder.append(root.val).append(",");
        preSerialize(root.left, builder);
        preSerialize(root.right, builder);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        LinkedList<String> list = new LinkedList<>();
        for (String s : split) {
            list.add(s);
        }
        return preDeserialize(list);
    }

    private TreeNode preDeserialize(LinkedList<String> list) {
        String first = list.removeFirst();
        //如果为# 说明节点为为null，则这个子树到头了
        if (first.equals("#")) {
            return null;
        }
        TreeNode treeNode = new TreeNode(Integer.valueOf(first));
        treeNode.left = preDeserialize(list);
        treeNode.right = preDeserialize(list);
        return treeNode;
    }
}
